#include <iostream>
#include <vector>
#include <string>
#include <string.h>
#include <climits>
using namespace std;
// 路径问题
class Solution1
{
public:
    int uniquePaths(int m, int n)
    {
        if (m == 0 && n == 0)
            return 1;
        // vector可以自动初始化数组为0！
        vector<vector<int>> dp(m + 1, vector<int>(n + 1)); // 二维数组多开一行和一列，作为虚拟节点
        dp[0][1] = 1;                                      // 也可以[1,0]位置为1start位置就有1种方法
        for (int i = 1; i <= m; ++i)                       // 我们最外面的一行一列虚拟节点因为vector创建数组自动初始化0，所以就都初始化完毕了
        {
            for (int j = 1; j <= n; ++j) // 所以行列都从1开始
            {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m][n];
        // for(int i = 0;i<=m;++i)
        // {
        //     for(int j = 0;j<=n;++j)
        //     {
        //         dp[i][j] = dp[i-1][j]+dp[i][j-1];
        //         // if(i==0 && j==1)
        //         //     dp[i][j] = 1;// start如果是终点，那么就为1，我们可以让[i,j]为1，也可以让[j][i]为1,这样start位置就有1种方法了
        //         // else if(i>0 && j>0)
        //         // {
        //         //     // 状态转移方程，该位置可以由上面位置和左边位置得到，所以方法就是上面位置方法数 + 左边位置方法数
        //         //     dp[i][j] = dp[i-1][j]+dp[i][j-1];
        //         // }
        //         // else
        //         //     dp[i][j] = 0;// 初始化用的，因为我们上面把start已经初始化为1了，可以根据start得到其他位置的值，所以全部为0
        //     }
        // }
        // return dp[m][n];
    }
};

//  路径问题II
class Solution2
{
public:
    int uniquePathsWithObstacles(vector<vector<int>> &obstacleGrid)
    {
        int row = obstacleGrid.size();
        int col = obstacleGrid[0].size();
        vector<vector<int>> dp(row + 1, vector<int>(col + 1));
        dp[0][1] = 1;

        for (int i = 1; i <= row; ++i)
        {
            for (int j = 1; j <= col; ++j)
            {
                // if(obstacleGrid[i-1][j-1] == 1)// 障碍物在我们的dp二维数组里面对应位置置0，表示该位置有障碍物，没有到达方法
                //     dp[i][j] = 0;
                // else
                //     dp[i][j]=dp[i-1][j]+dp[i][j-1];
                if (obstacleGrid[i - 1][j - 1] == 0)
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[row][col];
    }
};

// 珠宝的最高价值
class Solution3
{
public:
    int jewelleryValue(vector<vector<int>> &frame)
    {
        int row = frame.size();
        int col = frame[0].size();
        vector<vector<int>> dp(row + 1, vector<int>(col + 1));
        for (int i = 1; i <= row; i++)
        {
            for (int j = 1; j <= col; ++j)
            {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + frame[i - 1][j - 1]; // 上面和左边的dp最大值加上该位置的frame值，然后取最大值
            }
        }
        return dp[row][col];
    }
};

// 下降路径最小和
class Solution4
{
public:
    int minFallingPathSum(vector<vector<int>> &matrix)
    {
        int row = matrix.size();
        int col = matrix[0].size();
        vector<vector<int>> dp(row + 1, vector<int>(col + 2, INT_MAX));
        // 注意dp第一行的虚拟空间必须是0，不能是正无穷，而虚拟空间第一列和最后一列必须是正无穷
        // 如果dp第一行虚拟空间也是正无穷，那么dp第二行的正文就是【正无穷 + matrix第一行数据】
        // dp存放最短路径，所以dp正文第二行必须和matrix一样，因为matrix第一行的所有数据本身就是最短路径
        // dp虚拟空间第一列和最后一列必须是正无穷，因为这两列虚拟空间是不能对dp[i][j]进行干扰的，题目
        // 题目要求去最小值，那么虚拟空间第一列和最后一列为了避免干扰运算，因该初始化为正无穷大，保证虚拟空间是最大的，不参与运算
        for (int j = 0; j < col + 2; ++j)
            dp[0][j] = 0;
        for (int i = 1; i <= row; ++i)
        {
            for (int j = 1; j <= col; ++j)
            {
                dp[i][j] = min(min(dp[i - 1][j], dp[i - 1][j - 1]), dp[i - 1][j + 1]) + matrix[i - 1][j - 1];
            }
        }
        int min = dp[row][1]; // min = INT_MAX
        for (int i = 1; i <= col; i++)
        {
            if (min > dp[row][i])
                min = dp[row][i];
        }
        return min;
    }
};

// 最小路径和
class Solution
{
public:
    int minPathSum(vector<vector<int>> &grid)
    {
        int m = grid.size();
        int n = grid[0].size();
        // 为了防止dp虚拟空间对dp正文进行干扰，所以要初始化为正无穷大，不为无穷大就可能进行虚拟空间+grid数据
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, INT_MAX));
        // dp表中正文第一个数据[1][1]只能是grid的[0][0]值本身，又因为dp[1][1]上面和左边都是虚拟空间的正无穷大
        dp[0][1] = 0; // 所以是需要将dp虚拟空间[0][1]或者[1][0]置为0，方便使得dp[1][1]取得grid[0][0]值---> dp[1][1] = 0 + grid[0][0]
        // 但是因为有了dp[1][1]，需要后面dp正文部分都要取到前面已经有的正文数据，不能取到虚拟空间的值，所以其他虚拟空间值就要为正无穷
        for (int i = 1; i <= m; ++i)
        {
            for (int j = 1; j <= n; ++j)
            {
                dp[i][j] = min(dp[i][j - 1], dp[i - 1][j]) + grid[i - 1][j - 1];
            }
        }
        return dp[m][n];
    }
};

// 地下城游戏
class Solution
{
public:
    int calculateMinimumHP(vector<vector<int>> &d)
    {
        // dp[i][j]不能作为结尾，要作为起始。因为题目的要求表明了，dp[i][j]要受到下面或者右边数据的影响，不能让骑士死掉
        int m = d.size();
        int n = d[0].size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, INT_MAX)); // 求右边和下面的最小值，所以虚拟空间不需要运算，初始化为正无穷
        dp[m][n - 1] = dp[m - 1][n] = 1;                            // 救完公主，要剩下一滴血，所以终点右边和下面的虚拟空间初始化为1
        for (int i = m - 1; i >= 0; --i)                            // 从下往上，从右往左进行填表
        {
            for (int j = n - 1; j >= 0; --j)
            {
                dp[i][j] = min(dp[i][j + 1], dp[i + 1][j]) - d[i][j];
                dp[i][j] = max(1, dp[i][j]); // 如果我的d[i][j]是一个大血包，那么我骑士dp[i][j]都可以是负数血量救出公主，这是不合理的
            }
        }
        return dp[0][0];
    }
};

int main
{
    fsadf;
}
